/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
// 又是hash表
var detectCycle = function (head) {
  if (head == null) return null
  let slow = head, fast = head.next
  while (slow !== fast && slow && fast) {
    slow = slow.next
    if (fast.next) {
      fast = fast.next.next
    } else {
      fast = null
    }
  }
  // 判断是否有环
  if (fast == null) return null
  // 环的位置怎么找？
  let m = new Map()
  let ptr = head
  while (ptr) {
    if (m.has(ptr)) return ptr
    else m.set(ptr, 1)
    ptr = ptr.next
  }
}
// 快慢指针 太过臃肿继续优化
var detectCycle1 = function (head) {
  if (head == null) return null
  let slow = head, fast = head
  slow = slow.next
  if (fast.next)
    fast = fast.next.next
  while (slow !== fast && fast) {
    if (slow)
      slow = slow.next
    if (fast.next)
      fast = fast.next.next
    else
      fast = null
  }
  if (!fast) return null
  slow = head
  while (slow !== fast) {
    slow = slow.next
    fast = fast.next
  }
  return slow
}
var detectCycle2 = function (head) {
  if (head === null) return null
  let slow = head, fast = head
  while (true) { // 注意while true的使用
    if (fast == null || fast.next == null) return null
    slow = slow.next
    fast = fast.next.next
    if (slow === fast) break
  }
  slow = head
  while (slow !== fast) {
    slow = slow.next
    fast = fast.next
  }
  return slow
}